#include "octree.h"
#include "frustum.h"
#include "gameMath.h"

vector<Vector> debugLines;

// The current amount of subdivisions we are currently at.
// This is used to make sure we don't go over the max amount
int g_CurrentSubdivision = 0;

//This goes through all of the lines that we stored in our list and draws them
void CDebug::RenderDebugLines()				// This renders all of the lines
{
	glDisable(GL_LIGHTING);					// Turn OFF lighting so the debug lines are bright yellow

	glBegin(GL_LINES);						// Start rendering lines

		glColor3ub(255, 255, 0);			// Turn the lines yellow

		// Go through the whole list of lines stored in the vector m_vLines.
		for(unsigned int i = 0; i < debugLines.size(); i++)
		{
			// Pass in the current point to be rendered as part of a line
			glVertex3f(debugLines[i][0], debugLines[i][1], debugLines[i][2]);
		}	

	glEnd();								// Stop rendering lines

	// If we have lighting turned on, turn the lights back on
	//if(g_bLighting) 
		glEnable(GL_LIGHTING);
}


//This adds a debug LINE to the stack of lines
void CDebug::AddDebugLine(Vector vPoint1, Vector vPoint2)
{
	// Add the 2 points that make up the line into our line list.
	debugLines.push_back(vPoint1);
	debugLines.push_back(vPoint2);
}

//This adds a debug RECTANGLE to the stack of lines
void CDebug::AddDebugRectangle(Vector vCenter, float width, float height, float depth)
{
	// So we can work with the code better, we divide the dimensions in half.
	// That way we can create the cube from the center outwards.
	width /= 2.0f;	height /= 2.0f;	depth /= 2.0f;

	Vector vTopLeftFront = Vector(vCenter[0] - width, vCenter[1] + height, vCenter[2] + depth);
	Vector vTopLeftBack = Vector(vCenter[0] - width, vCenter[1] + height, vCenter[2] - depth);
	Vector vTopRightBack = Vector(vCenter[0] + width, vCenter[1] + height, vCenter[2] - depth);
	Vector vTopRightFront = Vector(vCenter[0] + width, vCenter[1] + height, vCenter[2] + depth);
	Vector vBottom_LeftFront = Vector(vCenter[0] - width, vCenter[1] - height, vCenter[2] + depth);
	Vector vBottom_LeftBack = Vector(vCenter[0] - width, vCenter[1] - height, vCenter[2] - depth);
	Vector vBottomRightBack = Vector(vCenter[0] + width, vCenter[1] - height, vCenter[2] - depth);
	Vector vBottomRightFront = Vector(vCenter[0] + width, vCenter[1] - height, vCenter[2] + depth);

	//Store the top front line of the box
	debugLines.push_back(vTopLeftFront);
	debugLines.push_back(vTopRightFront);

	// Store the top back line of the box
	debugLines.push_back(vTopLeftBack);
	debugLines.push_back(vTopRightBack);

	// Store the top left line of the box
	debugLines.push_back(vTopLeftFront);
	debugLines.push_back(vTopLeftBack);

	// Store the top right line of the box
	debugLines.push_back(vTopRightFront);
	debugLines.push_back(vTopRightBack);

	// Store the bottom front line of the box
	debugLines.push_back(vBottom_LeftFront);
	debugLines.push_back(vBottomRightFront);

	// Store the bottom back line of the box
	debugLines.push_back(vBottom_LeftBack);
	debugLines.push_back(vBottomRightBack);

	// Store the bottom left line of the box
	debugLines.push_back(vBottom_LeftFront);
	debugLines.push_back(vBottom_LeftBack);

	// Store the bottom right line of the box
	debugLines.push_back(vBottomRightFront);
	debugLines.push_back(vBottomRightBack);

	// Store the bottom front line of the box
	debugLines.push_back(vTopLeftFront);
	debugLines.push_back(vBottom_LeftFront);

	// Store the back left line of the box
	debugLines.push_back(vTopLeftBack);
	debugLines.push_back(vBottom_LeftBack);

	// Store the front right line of the box
	debugLines.push_back(vTopRightBack);
	debugLines.push_back(vBottomRightBack);

	// Store the front left line of the box
	debugLines.push_back(vTopRightFront);
	debugLines.push_back(vBottomRightFront);
}

//This clears all of the debug lines
void CDebug::Clear()						
{
	debugLines.clear();
}


COctree::COctree()
{
	InitOctree();	
}

COctree::~COctree()
{
	DestroyOctree();
}


//This initialize our octree data members
void COctree::InitOctree()
{
	m_bSubDivided = false;
	nodeWidth = 0; 
	m_TriangleCount = 0;
	g_EndNodeCount = 0;
	g_MaxSubdivisions = 5;
	g_MaxTriangles = 100;
	m_vCenter = Vector(0, 0, 0);
	m_pVertices = NULL;
	memset(m_pOctreeNodes, 0, sizeof(m_pOctreeNodes));	
}

//This sets our initial width of the scene, as well as our center point
void COctree::GetSceneDimensions(Vector *pVertices, int numberOfVerts)
{
	float maxWidth = 0, maxHeight = 0, maxDepth = 0;

	if(!pVertices || numberOfVerts <= 0) return;

	// Go through all of the vertices and add them up to eventually find the center
	for(int i = 0; i < numberOfVerts; i++)
	{
		// Add the current vertex to the center variable (Using operator overloading)
		m_vCenter = m_vCenter + pVertices[i];
	}

	// Divide the total by the number of vertices to get the center point
	m_vCenter[0] /= numberOfVerts;
	m_vCenter[1] /= numberOfVerts;	
	m_vCenter[2] /= numberOfVerts;

	int i;
	// Go through all of the vertices and find the max dimensions
	for(i = 0; i < numberOfVerts; i++)
	{
		float currentWidth  = fabsf(pVertices[i][0] - m_vCenter[0]);	
		float currentHeight = fabsf(pVertices[i][1] - m_vCenter[1]);		
		float currentDepth  = fabsf(pVertices[i][2] - m_vCenter[2]);	

		if(currentWidth  > maxWidth)	maxWidth  = currentWidth;
		if(currentHeight > maxHeight)	maxHeight = currentHeight;
		if(currentDepth > maxDepth)		maxDepth  = currentDepth;
	}

	maxWidth *= 2;		maxHeight *= 2;		maxDepth *= 2;

	// Check if the width is the highest value and assign that for the cube dimension
	if(maxWidth > maxHeight && maxWidth > maxDepth)
		nodeWidth = maxWidth;

	// Check if the height is the heighest value and assign that for the cube dimension
	else if(maxHeight > maxWidth && maxHeight > maxDepth)
		nodeWidth = maxHeight;

	// Else it must be the depth or it's the same value as some of the other ones
	else
		nodeWidth = maxDepth;
}


//This returns the center point of the new subdivided node, depending on the ID
Vector COctree::GetNewNodeCenter(Vector vCenter, float width, int nodeID)
{
	// Initialize the new node center
	Vector vNodeCenter(0, 0, 0);

	// Create a dummy variable to cut down the code size
	Vector vCtr = vCenter;

	// Switch on the ID to see which subdivided node we are finding the center
	switch(nodeID)							
	{
		case TOP_LEFT_FRONT:
			// Calculate the center of this new node
			vNodeCenter = Vector(vCtr[0] - width/4, vCtr[1] + width/4, vCtr[2] + width/4);
			break;

		case TOP_LEFT_BACK:
			// Calculate the center of this new node
			vNodeCenter = Vector(vCtr[0] - width/4, vCtr[1] + width/4, vCtr[2] - width/4);
			break;

		case TOP_RIGHT_BACK:
			// Calculate the center of this new node
			vNodeCenter = Vector(vCtr[0] + width/4, vCtr[1] + width/4, vCtr[2] - width/4);
			break;

		case TOP_RIGHT_FRONT:
			// Calculate the center of this new node
			vNodeCenter = Vector(vCtr[0] + width/4, vCtr[1] + width/4, vCtr[2] + width/4);
			break;

		case BOTTOM_LEFT_FRONT:
			// Calculate the center of this new node
			vNodeCenter = Vector(vCtr[0] - width/4, vCtr[1] - width/4, vCtr[2] + width/4);
			break;

		case BOTTOM_LEFT_BACK:
			// Calculate the center of this new node
			vNodeCenter = Vector(vCtr[0] - width/4, vCtr[1] - width/4, vCtr[2] - width/4);
			break;

		case BOTTOM_RIGHT_BACK:
			// Calculate the center of this new node
			vNodeCenter = Vector(vCtr[0] + width/4, vCtr[1] - width/4, vCtr[2] - width/4);
			break;

		case BOTTOM_RIGHT_FRONT:
			// Calculate the center of this new node
			vNodeCenter = Vector(vCtr[0] + width/4, vCtr[1] - width/4, vCtr[2] + width/4);
			break;
	}

	// Return the new node center
	return vNodeCenter;
}


//This figures out the new node information and then passes it into CreateNode()
void COctree::CreateNewNode(Vector *pVertices, Vector *pNormals, vector<bool> pList, int numberOfVerts,
					  	    Vector vCenter,	 float width,        int triangleCount, int nodeID)
{
	// This function helps us set up the new node that is being created.  We only
	// want to create a new node if it found triangles in it's area.  If there were
	// no triangle found in this node's cube, then we ignore it and don't create a node.

	// Check if the first node found some triangles in it
	if(triangleCount)		
	{
		Vector *pNodeNormals = new Vector [triangleCount * 3];
		Vector *pNodeVertices = new Vector [triangleCount * 3];
		int index = 0;

		for(int i = 0; i < numberOfVerts; i++)
		{
			if(pList[i / 3])	
			{
				pNodeVertices[index] = pVertices[i];
				pNodeNormals[index] = pNormals[i];
				index++;
			}
		}

		m_pOctreeNodes[nodeID] = new COctree;
		Vector vNodeCenter = GetNewNodeCenter(vCenter, width, nodeID);
		g_CurrentSubdivision++;
		m_pOctreeNodes[nodeID]->CreateNode(pNodeVertices, pNodeNormals, triangleCount * 3, vNodeCenter, width / 2);
		g_CurrentSubdivision--;
		delete [] pNodeVertices;
		delete [] pNodeNormals;
	}
}


//This is our recursive function that goes through and subdivides our nodes
void COctree::CreateNode(Vector *pVertices, Vector *pNormals, int numberOfVerts, Vector vCenter, float width)
{
	int numberOfTriangles = numberOfVerts / 3;
	m_vCenter = vCenter;
	nodeWidth = width;
	g_Debug.AddDebugRectangle(vCenter, width, width, width);

	if( (numberOfTriangles > g_MaxTriangles) && (g_CurrentSubdivision < g_MaxSubdivisions) )
	{
		m_bSubDivided = true;

		// Create the list of booleans for each triangle index
		vector<bool> pList1(numberOfTriangles);		// TOP_LEFT_FRONT node list
		vector<bool> pList2(numberOfTriangles);		// TOP_LEFT_BACK node list
		vector<bool> pList3(numberOfTriangles);		// TOP_RIGHT_BACK node list
		vector<bool> pList4(numberOfTriangles);		// TOP_RIGHT_FRONT node list
		vector<bool> pList5(numberOfTriangles);		// BOTTOM_LEFT_FRONT node list
		vector<bool> pList6(numberOfTriangles);		// BOTTOM_LEFT_BACK node list
		vector<bool> pList7(numberOfTriangles);		// BOTTOM_RIGHT_BACK node list
		vector<bool> pList8(numberOfTriangles);		// BOTTOM_RIGHT_FRONT node list
	
		// Create this variable to cut down the thickness of the code below (easier to read)
		Vector vCtr = vCenter;

		for(int i = 0; i < numberOfVerts; i++)
		{
			// Create some variables to cut down the thickness of the code (easier to read)
			Vector vPoint = pVertices[i];

			// Check if the point lines within the TOP LEFT FRONT node
			if( (vPoint[0] <= vCtr[0]) && (vPoint[1] >= vCtr[1]) && (vPoint[2] >= vCtr[2]) ) 
				pList1[i / 3] = true;

			// Check if the point lines within the TOP LEFT BACK node
			if( (vPoint[0] <= vCtr[0]) && (vPoint[1] >= vCtr[1]) && (vPoint[2] <= vCtr[2]) ) 
				pList2[i / 3] = true;

			// Check if the point lines within the TOP RIGHT BACK node
			if( (vPoint[0] >= vCtr[0]) && (vPoint[1] >= vCtr[1]) && (vPoint[2] <= vCtr[2]) ) 
				pList3[i / 3] = true;

			// Check if the point lines within the TOP RIGHT FRONT node
			if( (vPoint[0] >= vCtr[0]) && (vPoint[1] >= vCtr[1]) && (vPoint[2] >= vCtr[2]) ) 
				pList4[i / 3] = true;

			// Check if the point lines within the BOTTOM LEFT FRONT node
			if( (vPoint[0] <= vCtr[0]) && (vPoint[1] <= vCtr[1]) && (vPoint[2] >= vCtr[2]) ) 
				pList5[i / 3] = true;

			// Check if the point lines within the BOTTOM LEFT BACK node
			if( (vPoint[0] <= vCtr[0]) && (vPoint[1] <= vCtr[1]) && (vPoint[2] <= vCtr[2]) ) 
				pList6[i / 3] = true;

			// Check if the point lines within the BOTTOM RIGHT BACK node
			if( (vPoint[0] >= vCtr[0]) && (vPoint[1] <= vCtr[1]) && (vPoint[2] <= vCtr[2]) ) 
				pList7[i / 3] = true;

			// Check if the point lines within the BOTTOM RIGHT FRONT node
			if( (vPoint[0] >= vCtr[0]) && (vPoint[1] <= vCtr[1]) && (vPoint[2] >= vCtr[2]) ) 
				pList8[i / 3] = true;
		}	

		int triCount1 = 0;	int triCount2 = 0;	int triCount3 = 0;	int triCount4 = 0;
		int triCount5 = 0;	int triCount6 = 0;	int triCount7 = 0;	int triCount8 = 0;
		
		// Go through each of the lists and increase the triangle count for each node.
		for(int i = 0; i < numberOfTriangles; i++)  
		{
			// Increase the triangle count for each node that has a "true" for the index i.
			if(pList1[i])	triCount1++;	if(pList2[i])	triCount2++;
			if(pList3[i])	triCount3++;	if(pList4[i])	triCount4++;
			if(pList5[i])	triCount5++;	if(pList6[i])	triCount6++;
			if(pList7[i])	triCount7++;	if(pList8[i])	triCount8++;
		}
	
		CreateNewNode(pVertices, pNormals, pList1, numberOfVerts, vCenter, width, triCount1, TOP_LEFT_FRONT);
		CreateNewNode(pVertices, pNormals, pList2, numberOfVerts, vCenter, width, triCount2, TOP_LEFT_BACK);
		CreateNewNode(pVertices, pNormals, pList3, numberOfVerts, vCenter, width, triCount3, TOP_RIGHT_BACK);
		CreateNewNode(pVertices, pNormals, pList4, numberOfVerts, vCenter, width, triCount4, TOP_RIGHT_FRONT);
		CreateNewNode(pVertices, pNormals, pList5, numberOfVerts, vCenter, width, triCount5, BOTTOM_LEFT_FRONT);
		CreateNewNode(pVertices, pNormals, pList6, numberOfVerts, vCenter, width, triCount6, BOTTOM_LEFT_BACK);
		CreateNewNode(pVertices, pNormals, pList7, numberOfVerts, vCenter, width, triCount7, BOTTOM_RIGHT_BACK);
		CreateNewNode(pVertices, pNormals, pList8, numberOfVerts, vCenter, width, triCount8, BOTTOM_RIGHT_FRONT);
	}
	else
	{
		AssignVerticesToNode(pVertices, pNormals, numberOfVerts);
	}
}


//This allocates memory for the vertices to assign to the current end node
void COctree::AssignVerticesToNode(Vector *pVertices, Vector *pNormals, int numberOfVerts)
{
	m_bSubDivided = false;
	m_TriangleCount = numberOfVerts / 3;
	m_pVertices = new Vector [numberOfVerts];
	m_pNormals = new Vector [numberOfVerts];
	memset(m_pVertices, 0, sizeof(Vector) * numberOfVerts);
	memset(m_pNormals, 0, sizeof(Vector) * numberOfVerts);
	memcpy(m_pVertices, pVertices, sizeof(Vector) * numberOfVerts);
	memcpy(m_pNormals, pNormals, sizeof(Vector) * numberOfVerts);
	g_EndNodeCount++;
}

//Draw only the nodes that are in the frustum
void COctree::DrawOctree(COctree *pNode)
{
	//g_Debug.RenderDebugLines();

	//if(!pNode) return;
	//else if(g_Frustum.cubeInFrustum(pNode->m_vCenter[0], pNode->m_vCenter[1], 
	//								pNode->m_vCenter[3], pNode->nodeWidth / 2))

	//if(pNode->IsSubDivided())
	//{
	//	DrawOctree(pNode->m_pOctreeNodes[TOP_LEFT_FRONT]);
	//	DrawOctree(pNode->m_pOctreeNodes[TOP_LEFT_BACK]);
	//	DrawOctree(pNode->m_pOctreeNodes[TOP_RIGHT_BACK]);
	//	DrawOctree(pNode->m_pOctreeNodes[TOP_RIGHT_FRONT]);
	//	DrawOctree(pNode->m_pOctreeNodes[BOTTOM_LEFT_FRONT]);
	//	DrawOctree(pNode->m_pOctreeNodes[BOTTOM_LEFT_BACK]);
	//	DrawOctree(pNode->m_pOctreeNodes[BOTTOM_RIGHT_BACK]);
	//	DrawOctree(pNode->m_pOctreeNodes[BOTTOM_RIGHT_FRONT]);
	//}
	//else
	//{
	//	if(!pNode->m_pVertices) return;
	//	glBegin(GL_TRIANGLES);
	//		glColor3ub(0, 255, 0);
	//		Vector *pVertices = pNode->m_pVertices;
	//		Vector *pNormals = pNode->m_pNormals;
	//		int trianglesCount = pNode->GetTriangleCount() * 3;

	//		for(int i = 0; i < trianglesCount; i += 3)
	//		{
	//			glNormal3f(pNormals[i][0], pNormals[i][1], pNormals[i][2]);

	//			// Render the first point in the triangle
	//			glVertex3f(pVertices[i][0], pVertices[i][1], pVertices[i][2]);

	//			glNormal3f(pNormals[i + 1][0], pNormals[i + 1][1], pNormals[i + 1][2]);

	//			// Render the next point in the triangle
	//			glVertex3f(pVertices[i + 1][0], pVertices[i + 1][1], pVertices[i + 1][2]);

	//			glNormal3f(pNormals[i + 2][0], pNormals[i + 2][1], pNormals[i + 2][2]);

	//			// Render the last point in the triangle to form the current triangle
	//			glVertex3f(pVertices[i + 2][0], pVertices[i + 2][1], pVertices[i + 2][2]);
	//		}
	//	glEnd();
	//}
}


//This frees the memory allocated in the octree
void COctree::DestroyOctree()
{
	if( m_pVertices )
	{
		delete[] m_pVertices;	
		m_pVertices = NULL;
	}

	for(int i = 0; i < 8; i++)
	{
		if(m_pOctreeNodes[i])
		{
			delete m_pOctreeNodes[i];
			m_pOctreeNodes[i] = NULL;
		}
	}

	InitOctree();
}